package leetcode.hot100;

public class number44 {
    public static void main(String[] args) {
        int[]nums=new int[]{2,3,1,1,4};
        System.out.println(jump(nums));
    }
    public static int jump(int[] nums) {
        int[]dp=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            int step=nums[i];
            for(int j=step;j>=0;j--){
                if(i+j<nums.length){
                    if(dp[i+j]==0){
                        dp[i+j]=dp[i]+1;
                    }else {
                        dp[i+j]=Math.min(dp[i+j],dp[i]+1);
                    }
                }
            }
        }
        for(int i=0;i<nums.length;i++){
            System.out.print(dp[i]+" ");
        }
        System.out.println();
        return dp[nums.length-1];
    }
}
